class Solution {
public:
    int findParent(vector<int>& parent, int indexId) {
        if (parent[indexId] != indexId) {
            parent[indexId] = findParent(parent, parent[indexId]);
        }
        return parent[indexId];
    }

    void doUnion(vector<int>& parent, int indexA, int indexB) {
        parent[findParent(parent, indexA)] = findParent(parent, indexB);
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }

        int pa, pb;
        for (auto& edge : edges) {
            pa = findParent(parent, edge[0]);
            pb = findParent(parent, edge[1]);
            if (pa == pb) {
                return edge;
            } else {
                doUnion(parent, pa, pb);
            }
        }

        return vector<int>{};
    }
};